#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], size;//ph第k个插入数的值，hp第k个插入数的下标

void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u){
    int t = u;
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        heap_swap(u / 2, u);
        u /= 2;
    }
}

int main(){
    int n, m;
    cin >> n;
    while(n --){
        string op;
        cin >> op;
        if(op == "I"){
            int x;
            cin >> x;
            size ++;
            m ++;
            ph[m] = size, hp[size] = m;
            h[size] = x;
            up(size);
        }
        else if(op == "PM") cout << h[1] << endl;
        else if(op == "DM"){
            heap_swap(1, size);
            size --;
            down(1);
        }
        else if(op == "D"){
            int k;
            cin >> k;
            k = ph[k];
            heap_swap(k, size);
            size --;
            down(k), up(k);
        }
        else if(op == "C"){
            int k, x;
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}